#include <bits/stdc++.h>
using namespace std;

#include <unordered_map>
#include <vector>
using namespace std;

// 二叉树节点定义
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr)
    {
    }
};

class Solution
{
  public:
    // 主函数：根据前序和中序遍历重建二叉树
    TreeNode *reConstructBinaryTree(vector<int> &preOrder,
                                    vector<int> &vinOrder)
    {
        int n = preOrder.size();
        if (n == 0)
            return nullptr;

        // 建立哈希表：存储中序元素的值与索引映射
        unordered_map<int, int> indexMap;
        for (int i = 0; i < n; ++i)
        {
            indexMap[vinOrder[i]] = i;
        }

        // 调用递归函数构建二叉树
        return buildTree(preOrder, vinOrder, 0, n - 1, 0, n - 1, indexMap);
    }

  private:
    // 递归构建二叉树
    TreeNode *buildTree(vector<int> &pre, vector<int> &vin, int preStart,
                        int preEnd, int vinStart, int vinEnd,
                        unordered_map<int, int> &indexMap)
    {
        // 递归终止条件：当前子树无节点
        if (preStart > preEnd)
            return nullptr;

        // 前序遍历的第一个元素为当前子树的根节点
        int rootVal = pre[preStart];
        TreeNode *root = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int vinRootIndex = indexMap[rootVal];

        // 计算左子树节点数量
        int leftCount = vinRootIndex - vinStart;

        // 递归构建左子树
        root->left = buildTree(pre, vin, preStart + 1, preStart + leftCount,
                               vinStart, vinRootIndex - 1, indexMap);

        // 递归构建右子树
        root->right = buildTree(pre, vin, preStart + leftCount + 1, preEnd,
                                vinRootIndex + 1, vinEnd, indexMap);

        return root;
    }
};

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr)
    {
    }
};

class Solution
{
  public:
    TreeNode *reConstructBinaryTree(vector<int> &preOrder,
                                    vector<int> &vinOrder)
    {
        // write code here
    }
};



